141. Минимальная сумма цифр

Сколько натуральных чисел из промежутка [m, n] имеют наименьшую сумму цифр?

Вход. Два натуральных числа m и n (1 ≤ m ≤ n ≤ 10⁶).

Выход. Выведите количество натуральных чисел из промежутка [m, n] с наименьшей суммой цифр.

Пример входа	Пример выхода
1 100	3

РЕШЕНИЕ

элементарная задача

Анализ алгоритма

Переберем числа от m до n и найдем число с минимальной суммой цифр. Наименьшую возможную сумму цифр сохраним в переменной mn. Снова перебираем числа от m до n и подсчитываем количество чисел, сумма цифр которых равна mn. Количество таких чисел и будет ответом.

Реализация алгоритма

Функция sumd вычисляет сумму цифр числа n.

int sumd(int n)

{

if (n < 10) return n;

return sumd(n / 10) + n % 10;

}

Основная часть программы. Читаем входные данные.

scanf("%d %d", &m, &n);

Минимальную сумму цифр числа вычисляем в переменной mn. Перебираем числа от m до n и находим число с минимальной суммой цифр.

mn = 1000000000;

for (i = m; i <= n; i++)

{

temp = sumd(i);

if (temp < mn) mn = temp;

}

Снова перебираем числа от m до n и подсчитываем количество чисел, сумма цифр которых равна mn.

for (i = m; i <= n; i++)

if (mn == sumd(i)) res++;

Выводим ответ.

printf("%d\n", res);

Java реализация

import java.util.*;

class Main

{

public static int sumd(int n)

{

if (n < 10) return n;

return sumd(n / 10) + n % 10;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int m = con.nextInt();

int n = con.nextInt();

int min = 1000000000;

for(int i = m; i <= n; i++)

{

int temp = sumd(i);

if (temp < min) min = temp;

}

int res = 0;

for(int i = m; i <= n; i++)

if (min == sumd(i)) res++;

System.out.println(res);

con.close();

}

}